#include<iostream>
#include<vector>

class Solution {
public:

    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Ffind-minimum-in-rotated-sorted-array%2F
    int findMin(vector<int>& nums)
    {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left)/2;//区间可分为[单调递增区间]和[单调递增区间][单调递增区间（总是小于左区间值）]
            if(nums[mid] > nums[right]) left = mid + 1;//该题依旧判断二段性，倘若旋转最right的值定小于左区间最大值
            else right = mid;
        }
        return nums[left];
    }

    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fque-shi-de-shu-zi-lcof%2F
    int takeAttendance(vector<int>& records)
    {
        int left = 0, right = records.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        return records[left]==left ? left + 1:left;//倘若点名本就是到齐的那么就是最后一个没来（题目要求必定有一个没到）
    }


    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fmove-zeroes%2F
    void moveZeroes(vector<int>& nums) {
        int dest = -1, cur = 0;
        while(cur < nums.size())//倘若采用便利时间复杂度将是O(n^2)
        {
            if(nums[cur] != 0)
            {
                swap(nums[++dest], nums[cur]);//双指针时间复杂度O(n)
            }
            cur++;
        }
    }

};


